package com.sourcetrip.algorithm.abs;

import com.sourcetrip.algorithm.inter.UnionFind;

/**
 * @author: ZhouBert
 * @date: 2021/1/5
 * @description: 并查集抽象类 --
 * 限定于正整数
 * 设计：
 * 默认使用一维数组进行实现。
 * --
 *
 */
public abstract class AbstractUnionFind implements UnionFind {
	protected int[] parents;

	//region	constructor

	/**
	 * 构建固定容量的并查集
	 * 默认初始 parents 的元素的根节点指向自身，这样表示每个元素都是独立的集合
	 *
	 * @param capacity 并查集的容量
	 */
	public AbstractUnionFind(int capacity) {
		if (capacity < 1) {
			throw new IllegalArgumentException("capacity must be >= 1");
		}

		//初始化 并查集
		parents = new int[capacity];
		for (int i = 0; i < capacity; i++) {
			parents[i] = i;
		}

	}


	//endregion


	@Override
	public abstract int find(int v);

	@Override
	public abstract void union(int v1, int v2);

	/**
	 * 通过判断 v1 和 v2 的元素的根是否相同进行判断
	 *
	 * @param v1
	 * @param v2
	 * @return
	 */
	@Override
	public boolean isSame(int v1, int v2) {
		return find(v1) == find(v2);
	}

	//region	protected methods

	/**
	 * 对 v 元素进行范围检查
	 *
	 * @param v
	 */
	protected void rangeCheck(int v) {
		if (v < 0 || v >= parents.length) {
			throw new IllegalArgumentException("v is out of bounds");
		}
	}

	//endregion
}
